package com.atguigu.binaryTree;

import java.util.PriorityQueue;

public class MedianFinder {
    PriorityQueue<Integer> MaxPriority;
    PriorityQueue<Integer> MinPriority;
    public MedianFinder() {
        MaxPriority=new PriorityQueue<>((a, b) -> (b - a));
        MinPriority=new PriorityQueue<>((a, b) -> (a - b));
    }

    public static void main(String[] args) {
        MedianFinder medianFinder=new MedianFinder();
        medianFinder.addNum(6);

    }

    public void addNum(int num) {
        //大根堆为空，就置于大根堆
        if(MaxPriority.isEmpty()){
            MaxPriority.add(num);
            return;
        }
        if(num<=MaxPriority.peek()){
            MaxPriority.add(num);
            if(MaxPriority.size()-MinPriority.size()==2){
                MinPriority.add(MaxPriority.poll());
            }
        }else{
            MinPriority.add(num);
            if(MinPriority.size()-MaxPriority.size()==2){
                MaxPriority.add(MinPriority.poll());
            }
        }
    }

    public double findMedian() {

        if(MaxPriority.size()==MinPriority.size()){
            double tmp=MaxPriority.peek()+MinPriority.peek();
            return tmp/2;
        }else if(MaxPriority.size()>MinPriority.size()){
            return MaxPriority.peek();
        }else{
            return MinPriority.peek();
        }
    }
}
